In this paper we study conditions which guarantee the existence of perfectmatchings and perfect fractional matchings in uniform hypergraphs. We reducethis problem to an old conjecture by Erd\H{o}s on estimating the maximum numberof edges in a hypergraph when the (fractional) matching number is given, whichwe are able to solve in some special cases using probabilistic techniques.Based on these results, we obtain some general theorems on the minimum$d$-degree ensuring the existence of perfect (fractional) matchings. Inparticular, we asymptotically determine the minimum vertex degree whichguarantees a perfect matching in 4-uniform and 5-uniform hypergraphs. We alsodiscuss an application to a problem of finding an optimal data allocation in adistributed storage system.
展开▼
机译:在本文中,我们研究了保证均匀超图上存在完美匹配和完美分数匹配的条件。我们通过用Erd \ H {o} s将这个问题简化为一个古老的猜想,即在给出(分数)匹配数时估计超图中的最大边数,在某些特殊情况下,我们可以使用概率技术来解决这个问题。结果,我们获得了关于最小$ d $度的一些一般性定理,以确保存在完美(分数)匹配。特别是,我们渐近地确定了最小顶点度,该最小顶点度保证了4均匀和5均匀超图的完美匹配。我们还讨论了在分布式存储系统中寻找最佳数据分配问题的应用。
展开▼